package question;

public class Q0912 {

	/**
	 * 题目描述
	 * 最后算法题：给一个数组和 target 值，找出长度最长的且和等于 target 的连续子数组的长度 
	 * @param args
	 */
	public static void main(String[] args) {
		int [] nums = new int[20];
		for(int i = 0 ; i < 20 ; i++) {
			nums[i] = i;
		}
		int target = 5;
		//int result = find(nums,target);
		//int result1 = maxLenthSubArray(nums,target);
		//int result2 = find2(nums,target);
		int result3 = maxLenthSubArray(nums, target);
		System.out.println(result3);
	} 
	
	public static int find(int[] nums, int target) {
		/**
		 * 第一种方法
		 * 时间复杂度:o(n2)
		 */
		int len = nums.length;
		if(len == 0) {
			return -1;
		}
		int maxLen = -1;
		for(int i = 0 ; i < len ; i ++) {
			int sum = 0;
			for(int j = i ; j < len ; j++) {
				sum = sum + nums[j];
				if(sum == target && (j-i+1) > maxLen) {
					maxLen = (j-i+1);
				}
			}
		}
		return maxLen;
	}
	
	public static int find2(int[] nums, int target) {
		/**
		 * 第二种方法:
		 * 目标复杂度:o(n)
		 */
		int [] dis = new int[nums.length];
		dis[0] = nums[0];
		//每一个位置的值都是前面的值（包括本位置)的和
		for(int i = 1 ; i < nums.length ; i++) {
			dis[i] = nums[i] + dis[i-1];
		}
		int start = 0;
		int end = nums.length -1;
		int windowLen = nums.length;
		int flag = 0;
		
		while(windowLen > 0) {
			
			if(flag == 0) {
				end = windowLen - 1;
				start = 0;
			}
			if(windowLen == 1) {
				flag ++;
				if(nums[start] == target) {
					return 1;
				} else {
					start++;
					if(start < nums.length)
						continue;
					else
						return -1;
				}
			}
			if((dis[end] - dis[start] + nums[start]) == target) {
				return windowLen;
			} else {
				end++;
				start++;
				if(end < nums.length) {
					flag++;
					continue;
				} else {
					windowLen --;
					flag = 0;
				}
			}
		}
		return -1;
	}
	
	

	 public static int maxLenthSubArray(int[] nums, int target) {
	        int ans = 0;
	        int[] d = new int[nums.length];
	        d[0] = nums[0];
	        for (int i = 1; i < nums.length; i++) {
	            d[i] = d[i - 1] + nums[i];
	        }
	        int pre = 0;
	        int last = 1;
	        while (last < nums.length && pre < nums.length){
	            if (d[last] - d[pre] == target){
	                if (ans < last - pre)
	                    ans = last - pre;
	                last++;
	                continue;
	            }
	            if (d[last] - d[pre] > target)
	                pre++;
	            if (d[last] - d[pre] < target)
	                last++;
	            System.out.println(last + " " + pre);  // 看双指针的移动
	        }
	        return ans;
	    }
}
